package com.dragon.datastructure.queue;

import java.util.ArrayDeque;
import java.util.LinkedList;

/**
 * 数组队列的执行性能分析
 * ----------------------------------------------
 * arrayDeque insert 10000000个元素所用时间:2521
 * arrayDeque poll 10000000个元素所用时间:17
 * <p>
 * linkedList insert 10000000个元素所用时间:5481
 * linkedList poll 10000000个元素所用时间:124
 * <p>
 * -----------------------------------------------
 * arrayDeque insert 1000000个元素所用时间:24
 * arrayDeque poll 1000000个元素所用时间:14
 * <p>
 * linkedList insert 1000000个元素所用时间:32
 * linkedList poll 1000000个元素所用时间:21
 * ------------------------------------------------
 * <p>
 * ArrayDeque底层是循环数组，既可以做队列使用，又可以做栈使用；
 * ArrayDeque与LinkedList都是Deque接口的实现类，两者的差别是底层的数据结构不同，LinkedList底层基于双向链表，内存开销高于ArrayDeque,
 * 因为LinkedList每一个节点不仅要存放数据，还要维护前后两个节点的引用。
 * 在数据量量小的时候，两者的效率差别不大，在大数据量的情况下，ArrayDeque作为栈或者是队列 的性能是高于 LinkedList，因为ArrayDeque
 * 底层是循环数组，它添加到队列尾部直接插入到数组尾部，移动 一下tail指针，很方便；而LinkedList插入到链表尾部，需要创建节点，维护节点与节点之间的关联关系
 * <p>
 * notes: ArrayDeque不支持插入null值，因为ArrayDeque的poll()方法底层有可能作为null来返回代表队列为空了，所以严格限制不能插入null值
 *
 * @author dragon
 * @since 2019/12/19
 */
public class ArrayDequePerformanceAnalysis {


    public static void main(String[] args) {
//        arrayDequeOfferAndPoll(1_000_000);
        linkedListOfferAndPoll(1_000_000);

    }


    public static void arrayDequeOfferAndPoll(int loopCount) {
        long insertStartMills = System.currentTimeMillis();
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < loopCount; i++) {
            deque.offer(i);
        }
        long insertEndMills = System.currentTimeMillis();
        System.out.println("arrayDeque insert " + loopCount + "个元素所用时间:" + (insertEndMills - insertStartMills));

        long pollStartMills = System.currentTimeMillis();
        while (true) {
            Integer pollResult = deque.poll();
            if (pollResult == null) {
                break;
            }
        }
        long pollEndMills = System.currentTimeMillis();
        System.out.println("arrayDeque poll " + loopCount + "个元素所用时间:" + (pollEndMills - pollStartMills));

    }

    public static void linkedListOfferAndPoll(int loopCount) {
        long insertStartMills = System.currentTimeMillis();
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < loopCount; i++) {
            linkedList.offer(i);
        }
        long insertEndMills = System.currentTimeMillis();
        System.out.println("linkedList insert " + loopCount + "个元素所用时间:" + (insertEndMills - insertStartMills));

        long pollStartMills = System.currentTimeMillis();
        while (true) {
            Integer pollResult = linkedList.poll();
            if (pollResult == null) {
                break;
            }
        }
        long pollEndMills = System.currentTimeMillis();
        System.out.println("linkedList poll " + loopCount + "个元素所用时间:" + (pollEndMills - pollStartMills));
    }
}
